class hashTable {
    constructor() {
        // 属性
        this.size = 7;
        this.storage = new Array(this.size);
        this.count = 0;
    }

    // 哈希函数
    hashFunction(str) {
        // 初始化hashCode
        let hashCode = 0

        // 根据str,计算hashCode
        for (let i = 0; i < str.length; i++) {
            hashCode = hashCode * 37 + str[i].charCodeAt()
        }
        // 根据size取余
        return hashCode % this.size
    }

    // 添加或者修改数据
    put(key, value) {
        // 1 获取对应hash值
        let index = this.hashFunction(key);

        // 2 判断对应位置是否存在数据
        let bucket = this.storage[index];
        if (!bucket) {
            bucket = [];
            this.storage[index] = bucket
        }

        // 3 遍历bucket，如果之前存在key,则修改数据

        for (let i = 0; i < bucket.length; i++) {
            let item = bucket[i];
            if (item[0] == key) {
                item[1] = value
                return
            }
        }
        // 4 如果不存在key，则添加新数据
        bucket.push([key, value])
        this.count++;

        // 5 如果装载因子大于0.75,则扩容
        if(this.count > this.size*0.75){
            this.resize(Math.floor(this.size*2))
        }

    }

    // 获取数据
    get(key) {
        // 1 根据 key 获取hashCode
        let index = this.hashFunction(key);

        // 2 对应位置是否存在bucket
        let bucket = this.storage[index];
        if (!bucket) return null;

        // 3 判断bucket中是否存在key
        for (let i = 0; i < bucket.length; i++) {
            let item = bucket[i];
            if (key === item[0]) {
                return item[1]
            }
        }
        // 4 bucket不否存在key
        return null

    }

    // 删除数据
    remove(key) {
        // 1 根据 key 获取hashCode
        let index = this.hashFunction(key);

        // 2 对应位置是否存在bucket
        let bucket = this.storage[index];
        if (!bucket) return null;

        // 3 遍历bucket是否存在key数据
        for(let i=0;i<bucket.length;i++){
            let item = bucket[i];
            if(item[0] === key){
                bucket.splice(i,1);
                this.count--;
                
                // 判断装载因子小于0.25，对哈希表减容
                if( this.size > 7 && this.count < this.size*0.25){
                    this.resize(Math.floor(this.size*0.5))
                }

                return item[1]
            }
        }

        // 4 bucket中不存在数据
        return null
    }

    // 数组扩容
    resize(size){
        // 存储旧数据
        let oldStorage = this.storage;
        
        // 清空数据，并扩容
        this.size = this.getPrimeNum(size);
        this.storage = new Array(this.size);
        this.count = 0;
         
        // 重新存储
        for(let i=0;i<oldStorage.length;i++){
            let bucket = oldStorage[i]
            if(bucket){
              for(let j=0;j<bucket.length;j++){
                  let item = bucket[j]
                  this.put(item[0],item[1])
              }
            }
        }
    }

    // 判断是否是一个质数
      isPrimeNum(num){
        if(num == 1 || num==2)return true

        let k = Math.floor(Math.sqrt(num))
         
        for(let i=2;i<=k;i++){
              if(num % i == 0){
                  return false
              }
        }
        return true

    }

    // 获取质数
     getPrimeNum(num){
        while(!this.isPrimeNum(num)){
            num++
        }
        return num
    }



    // 判断数据是否为空
    isEmpty(){
        return this.count === 0
    }
  
}




var k = new hashTable();
k.put("jianglang99", { name: "11" })
k.put("jianglng1", { name: "22" })
k.put("jianglng2", { name: "33" })
k.put("jianglng3", { name: "44" })
k.put("jianglng4", { name: "11" })
k.put("jiangln88", { name: "11" })
k.put("jianglng5", { name: "11" })
k.put("jianglng7", { name: "11" })

console.log(k)

console.log(k.get("jianglang"))
console.log(k.remove("jianglang"))
console.log(k.get("jianglang"))

console.log(k)